Convex Structures

Back

(A) Convex Sets and Convex Hulls
(B) The Separating Hyperplane Theorem
(C) Convex Cones and Inequalities
(D) The Minkowski-Farkas Lemma

Selected References

Appeals to convex stuctures in mathematics are few and far between. Rather than dealing with the particular case of convex sets, much of mathematics prefers to concentrate on more general linear subspaces. However, convex structures are central in modern economics -- particularly with the development of linear programming and the discovery (by economists) of the Separating Hyperplane Theorem in the 1940s - which allowed them to reformulate much of the central tenets of Walrasian economics without unecessary and restrictive differentiability assumptions. Convexity was the organizing principle of mathematical economics - particularly as practiced by those associated with the Cowles Commission (Koopmans, Debreu, Arrow, etc.) throughout the 1950s. The crucial contribution to this transformation was John von Neumann's 1937 paper written through the Vienna Colloquium.

Most of the important mathematical arguments contained here and in the subsequent sections - axiomatic reasoning, convexity arguments, linear systems of inequalities, saddlepoints, programming and duality relationships and fixed-point theorems were all introduced to economics by John von Neumann (1937). Adoption and extension of these tools were relatively swift and revolutionized mathematical economics and drew it away from the "Paretian" use of differential calculus and into axiomatic reasoning. For more reflections on this transformation in mathematical approach, see Debreu (1984, 1986, 1991), Khan (1993), Mirowski and Weintraub (1994) and Weintraub (1985).

(A) Convex Sets and Convex Hulls

We begin with a simple definition:

Convex: the set X Í Rⁿ is a "convex set" if for every x, y Î X and any l Î (0, 1), then l x + (1-l)y Î X.

Now we turn to an often useful theorem:

Theorem: Let {X_n} be a collection of convex sets. Then Ç _nX_n is a convex set.

Proof: If x, y Î Ç _nX_n then x, y Î X_n for all n. Since X_n is convex, then for any l Î (0, 1), we have l x + (1-l )y Î X_n for all n. Thus, for any l Î (0, 1), l x + (1-l )y Î Ç _nX_n.§

It is easy to show that È _nX_n is not convex.

Convex Hull: If the set co(X) Í Rⁿ is the smallest convex set in Rⁿ containing X, then co(X) is the "convex hull" of X.

Thus, we can readily notice that co(X) is generated by all convex linear combinations of elements of X, i.e. the convex hull of X merely equals all points å _i l _ix_i where x_i Î X and l _i ³ 0 and å _{il i} = 1.

Theorem: For every non-empty subset X Í Rⁿ, the convex hull of X, co(X), exists.

Proof: Let {X_n} be the collection of all convex sets containing X, i.e. X Í X_n for all X_n. Since Rⁿ is itself convex, then {X_n} is non-empty. From the earlier theorem, we know that the intersection is convex, thus Ç _n X_n is convex and itself contains X. Thus, define co(X) = Ç _nX_n which is the smallest convex set containing X.§

(B) The Separating Hyperplane Theorem (SHT)

The Separating Hyperplane Theorem is merely a version of the Hahn-Banach Theorem for functional analysis - and really states nothing much more complicated than that two convex sets can be separated by a line ("hyperplane") with one of the convex sets lying on one side of it and the other set sitting on the other. However, the importance of the "discovery" of the SHT by economists in the 1940s and 1950s can hardly be overstressed - for in this "separating hyperplane", economists saw "price lines" and in the convex sets they saw the typical sets in economics on which these price lines would sit - those defined by indifference curves, budget constraints, production possibility frontiers, etc. What was merely a supposition before the 1950s - i.e. "there is a set of prices such that..." was now translated into "there is a separating hyperplane..." and thereby confirmed.

Generally, a hyperplane is a linear subspace of one dimension less than the space in which it sits (thus diagramatically, a "hyperplane" is a line drawn in a two-dimensional space or a plane drawn in three-dimensional space). It is defined as follows:

Hyperplane: A given non-zero vector p Î Rⁿ and a scalar c Î R define a "hyperplane" H(p, c) in Rⁿ where:

H(p, c) = {x Î Rⁿ | p·x = c}

Thus, H(p, c) Í Rⁿ is a linear subspace. A hyperplane divides the space into two closed "half-spaces" H^³(p, c) = {x Î Rⁿ | p·x ³ c} and H^£(p, c) = {x Î Rⁿ | p·x £ c} which are the spaces "above" and "below" the hyperplane respectively. These half-spaces are convex:

Theorem: (Convexity of Half-Spaces) For all non-zero p Î Rⁿ and c Î R, the set H^£ = {x Î Rⁿ | p·x £ c} is convex.

Proof: Let x, y Î H^£ . Then for all l Î [0, 1], p·(l x + (1-l )y) = l (p·x) + (1-l )(p·y). Since x, y Î H^£, then p·x £ c and p·y £ c thus, l (p·x) + (1-l )(p·y) £ l c + (1-l )c = c and thus p·(l x + (1-l )y) £ c. Thus, l x + (1-l )y Î H^£ .§

And we can do the same for H^³.

Supporting Hyperplane: A hyperplane H is said to be a "supporting hyperplane" to a convex set X if X is contained within one of the halfspaces of H and the boundary of X has points in comon with H, i.e. H is a supporting hyperplane to X if inf{p·x | x Î X} = c (thus X Í X³ ) or sup{p·x | x Î X} = c (thus X Í X£ ).

Separating Hyperplane: Two convex sets, A and B, are "separable by a hyperplane" if there exists a hyperplane H(p, c) such that A and B belong to different half-spaces, i.e. such that A Í {x Î Rⁿ | p·x ³ c} and B Í {x Î Rⁿ | p·x £ c}. They are "strictly separable" if either A Ì {x Î Rⁿ | p·x > c} and/or B Ì {x Î Rⁿ | p·x < c}.

This is easy to visualize diagramatically as in Figure 2.  Let us now turn to the SHT. We first prove that we can separate a convex a point from a non-empty convex set, before proving we can separate two disjoint convex sets.

Theorem: (Separation of Point from Convex Set) Let X be a non-empty and convex set in Rⁿ. Let y Î X^c. Then there exists a vector p Î Rⁿ where p ¹ 0 and inf{px | x Î X} > py (i.e. the sets {y} and X are separable).

Proof: If X is convex, then its closure cl(X) is also convex. Let x° be a boundary point of X such that ||x° - y|| = inf_{xÎ X} ||x - y||, i.e. x° is the point in cl(X) closest to y. As cl(X) is convex, then if x Î X, then l x + (1-l )x° Î cl(X) for any l Î (0, 1] - or, simply, x° + l (x - x° ) Î cl(X). But as ||x⁰ - y|| £ ||x - y|| for all x Î cl(X), then ||x⁰ - y|| £ ||(x⁰ + l (x-x⁰)) - y||

or:

||x⁰ - y|| £ ||(x⁰ - y) + l (x-x⁰)||

Thus squaring:

||x⁰ - y||² £ ||(x⁰ - y) + l (x-x⁰)||²

But as ||x||² = x·x, then:

(x⁰ - y)(x⁰ - y) £ [(x⁰ - y) + l (x - x⁰)]·[(x⁰ - y) + l (x - x⁰)]

or:

(x⁰ - y)(x⁰ - y) £ (x⁰ - y)(x⁰ - y) + 2l (x - x⁰)·(x⁰ - y) + l ²(x - x⁰)(x - x⁰)

thus:

2l (x - x⁰)·(x⁰ - y) + l ²(x - x⁰)(x - x⁰) ³ 0

Thus, it must be that (x - x⁰)·(x⁰ - y) ³ 0 which implies that x·(x⁰ - y) ³ x⁰·(x⁰ - y). But by the property of inner product, if x⁰ ¹ y, then (x⁰ - y)(x⁰ - y) > 0, and thus x⁰(x⁰ - y) > y(x⁰ - y), thus combining the two inequalities:

x·(x⁰ - y) ³ x⁰·(x⁰ - y) > y(x⁰ - y)

Define p = (x⁰ - y), then if p ¹ 0 then the inequalities imply:

x·p ³ x⁰·p > y·p

thus, inf{x·p | x Î X} ³ x⁰·p > y·p. Thus, letting c = x⁰·p, then:

(i) x·p ³ c for all x Î X

(ii) c > y·p for {y}.

Thus, {y} and X are separated by the hyperplane H(p, c) = {x Î Rⁿ | x·p = c}.§

The foregoing proof is illustrated in Figure 1 (where z = l x + (1-l )x⁰) for two-dimensional Euclidian space (R²).

Figure 1 - Separation of Point from Set

We can now turn to the main Separating Hyperplane Theorem:

Theorem: (Separating Hyperplane Theorem) Let X and Y be two non-empty, convex sets in Rⁿ with no interior point in common, then there exists a pair (p c) where p Î Rⁿ ¹ 0 and c Î R such that:

px ³ c    " x Î X

py £ c " y Î Y

i.e. there is a hyperplane H(p, c) which separates X and Y.

Proof: Define X - Y = {x - y Î Rⁿ | x Î X, y Î Y} which is convex. Then, 0 Ï int(X-Y) (if it was, i.e. if 0 Î int(X - Y), then there is an x Î int(X) and y Î int(Y) such that x - y = 0, or simply x = y, i.e. there is an interior point in common). Thus, we can separate 0 from X-Y, i.e. there exists a p Î Rⁿ where p ¹ 0 and a c Î R such that p·(x-y) ³ c and p·0 £ c. As p·0 = 0, then p·(x-y) ³ 0, thus px ³ py for all x Î A and y Î B, or simply there is a c Î R such that px ³ c for all x Î X and py £ c for all y Î Y for all y Î Y. §

An example of this in a two-dimensional space can be seen in Figure 2.

Figure 2 - Separation of two convex sets

Of course, there is also a "strict" SHT which is as follows:

Theorem: (Strict SHT) Let X and Y be two closed, convex sets in Rⁿ with no points in common and at least one of which is bounded, then there exists a pair (p c) where p Î Rⁿ ¹ 0 and c Î R such that:

px > c " x Î X

py < c " y Î Y

i.e. there is a hyperplane H(p, c) which strictly separates X and Y.

Proof: Now, X and Y are closed thus, if either X or Y is bounded, then X - Y is closed as well and, as they have no points in common, then 0 Ï X-Y. Consequently, the rest of the proof follows from the previous theorem on the separation of a point 0 from set X-Y.§

(C) Convex Cones and Inequalities

Cone: X is a cone with vertex at the origin if for any x Î X and any scalar a ³ 0, then a x Î X.

Convex Cone: X is a "convex cone" if for any x, y Î X and any scalars a ³ 0 and b ³ 0, then a x + b y Î X.

Thus a convex cone is always convex always contains the origin. See the diagram below for an example in R².

Spanning: The "convex cone spanned by Y" is the smallest convex cone that contains the set Y, i.e.

C(Y) = {å _i l _i y_i ½ for all i = 1, .., n, l _i ³ 0, y_i Î Y and n arbitrary}

In Figure 3, X = C(Y), i.e. X is the convex cone spanned by Y.

Dual Cone: The "dual" X* of a convex cone X is the set {p Î Rⁿ | p·x £ 0 for all x Î X}.

An example of the dual X* of the convex cone X is shown in Figure 3, for two-dimensional Euclidian space.

Figure 3 - Convex Cones

The dual convex cone is always closed regardless of whether the original convex cone is closed or not. X** is the dual of the dual convex cone which, obviously, must be related to the original convex cone X. This is as follows:

Theorem: (Closedness of Dual Cone) If X is a convex cone, then X Í X** (where X = X** if and only if X is closed).

Proof: By definition of X*, if x Î X, then for all p Î X*, p·x £ 0. But p·x = x·p, so x·p £ 0, thus x Î X**. Thus, X Í X**. If X is closed, we shall prove also that X** Í X. Now, suppose x Ï X. Since X is closed and convex, then by the Separating Hyperplane Theorem, there is a p Î Rⁿ such that p·y £ p·x for all y Î X. But since X is a cone, then p·y £ 0 £ p·x. Thus, x·p ³ 0. Thus, if p Î X* (i.e. p·y £ 0) then x Ï X** (as x·p ³ 0). Thus, x Ï X Þ x Ï X**, thus X** Í X. Thus, combining with the first part, we see that X = X**.§

(D) The Minkowski-Farkas Lemma

The Minkowski-Farkas Lemma - sometimes only referred to as "Farkas's Theorem" is a highly useful result- particularly in linear programming, where we define primal and dual problems. It is effectively a corrollary of a basic theorem of the "alternative" which is, in turn, based on the Separating Hyperplane Theorem.

Theorem: (Basic Theorem of the Alternative) Let A be a m ´ n real matrix and b Î R^m, then exactly one of the following alternatives is true (but not both). Either:

(i) Ax = b has a non-negative solution x ³ 0.

or

(ii) yA ³ 0 and y·b < 0 has a solution y.

Proof: We go through several steps.

(i) Þ not (ii): Suppose that Ax = b has a non-negative solution x (so (i) holds). Then premultiplying by y, then yAx = yb. Then (ii) cannot hold. If it did, i.e. if yA ³ 0, then we see that yAx ³ 0 because x ³ 0 from (i). But, if so, then it must be that yb ³ 0, which contradicts (ii). Thus, not (ii).

not (i) Þ (ii): Let X be the convex cone spanned by columns a¹, .., aⁿ of A, i.e.

X = {a Î Rⁿ | a = å _il _iaⁱ, l _i ³ 0, i = 1, .., n}

Suppose that Ax = b has no non-negative solution. Then b Ï X. Since X is closed, then by the Separating Hyperplane Theorem, there is a vector y Î R^m such that y·a > y·b for all a Î X. Since X contains the origin, then 0 = y·0 > y·b. Supose that not yA ³ 0. Thus, there is a column in A, say a^k such that y·a^k < 0. Since X is a cone and a^k Î X, then a a^k Î X for all a > 0. Thus, for sufficiently large a , then y·(a a^k) = a (y·a^k) < y·b. But this contradicts separation. Thus, y·aⁱ ³ 0 for all columns aⁱ of A. Thus yA ³ 0. Thus, (ii) holds.§

The Minkowski-Farkas Lemma follows as a corrollary to the above. Namely:

Theorem: (Minkowski-Farkas Lemma) Let A be a m ´ n real matrix with column vectors a¹, .., aⁿ Î R^m and b Î R^m. Then l ·b ³ 0 for all l Î R^m such that l A ³ 0 if and only if there exists non-negative vector x = (x₁, ..., x_n) such that Ax = b.

Proof: Since l ·b ³ 0 for all l Î R^m such that l A ³ 0, then there can be no l such that l A ³ 0 and l ·b < 0. But then, by the previous theorem of the alternative, it must be that Ax = b for some non-negative x Î Rⁿ.§

Thus, in short, the Minkowski-Farkas Lemma states that if l ·b ³ 0 for all l such that l A ³ 0 , then Ax = b has a non-negative solution x ³ 0. The applications of the Minkowksi Lemma are numerous - to duality theorems in linear programming, the Kuhn-Tucker theorem and in zero-sum games.

This is, of course, merely a formal result - see Gale (1960: p.44) or Takayama (1974: p.46-7) for the intuition behind these results, which can be represented graphically in Figure 4 where we have, for illustration, decomposed matrix A into columns with vectors a¹, a² and a³. The convex cone spanned by these vectors (i.e. matrix A) is represented by the shaded area X in the diagram.

Figure 4 - Minkowski-Farkas Lemma

Let us now see the basic theorem of the alternative. The claim that Ax = b has no non-negative solution x implies that b does not lie in this convex cone, i.e. b Ï X (as is seen in the figure). But then the basic theorem of the alternative claims that this implies there is a y such that yb < 0 and yA ³ 0, i.e. there is a y that forms an obtuse angle with b and an acute angle with every vector aⁱ. It is easy to notice geometrically that this implies that there is a hyperplane H(y, 0) that is orthogonal to y and has the cone X on one side and b on the other (thus H(y, 0) = {x Î Rⁿ | y·x = 0} is separating hyperplane we obtain with the SHT which separates the cone X and the point b. The Minkowski-Farkas Lemma is merely the reverse of this.

Selected References

Kim C. Border (1985) Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge, UK: Cambridge University Press.

Gerard Debreu (1959) Theory of Value: An axiomatic analysis of economic equilibrium. New York: Wiley.

Gerard Debreu (1984) "Economic Theory in a Mathematical Mode", American Economic Review, Vol. 74 (3) p.267-78.

Gerard Debreu (1986) "Theoretic Models: Mathematical form and economic content", Econometrica, Vol. 54 (6), p.1259-70.

Gerard Debreu (1991) "The Mathematization of Economic Theory", American Economic Review, Vol 81 (1), p.1-7.

David Gale (1960) The Theory of Linear Economic Models. New York: McGraw-Hill.

M. Ali Khan (1993) "The Irony In/Of Economic Theory", MLN, Vol. 108 (4), p.759-803.

Philip Mirowski and E. Roy Weintraub (1994) "The Pure and the Applied: Bourbakism comes to America", Science in Context, Vol. 7 (2), p.245-72.

J. von Neumann (1937) "A Model of General Economic Equilibrium", in K. Menger, editor, Ergebnisse eines mathematischen Kolloquiums, 1935-36. 1945 Translation, Review of Economic Studies, Vol. 13 (1), p.1-9.

Hukukane Nikaido (1968) Convex Structures and Economic Theory. New York: Academic Press.

Herbert Scarf (1973) The Computation of Economic Equilibria. (with the collaboration of Terje Hansen), New Haven: Yale University Press.

Akira Takayama (1974) Mathematical Economics. 1985 (2nd) edition, Cambridge, UK: Cambridge University Press.

E. Roy Weintraub (1985) General Equilibrium Analysis: Studies in appraisal. Cambridge, UK: Cambridge University Press.

Back

Top

Selected References

Next